<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>dp</title>
</head>

<body>
    <script>
        //最短路径
        /* var minPathSum = function (grid) {
            var n = grid.length;
            var m = grid[0].length;
            var dp = Array.from(new Array(n), () => new Array(m));
            for (var i = 0; i < n; i++) {
                for (var j = 0; j < m; j++) {
                    if (i != 0 && j != 0) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                    } else if (i == 0 && j != 0) {
                        dp[i][j] = dp[i][j - 1] + grid[i][j];
                    } else if (i != 0 && j == 0) {
                        dp[i][j] = dp[i - 1][j] + grid[i][j];
                    } else if (i == 0 && j == 0) {
                        dp[i][j] = grid[i][j];
                    }

                }
            }
            console.log(dp)
            return dp[n - 1][m - 1];
        };
        minPathSum([
            [1, 3, 1],
            [1, 5, 1],
            [4, 2, 1]
        ]) */
        //斐波那契数列
        /* var Fibonacci = function (n) {
            if (n < 0) return n
            let Memo = new Array(n + 1)
            Memo[0] = 0
            Memo[1] = 1
            for (let i = 2; i <= n; i++) {
                Memo[i] = Memo[i - 1] + Memo[i - 2]
            }
            return Memo[n]
        }
        console.log(Fibonacci(9)) */
        //钢条切割
        const p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

        function cut_rod(n) {
            let r = [0, 1]
            let leftLength = [0, 1]
            let solution = []
            for (let i = 2; i <= n; i++) {
                let max = p[i]
                leftLength[i] = i
                for (let j = 1; j <= i; j++) {
                    let sum = p[j] + r[i - j]
                    if (sum > max) {
                        max = sum
                        leftLength[i] = j
                    }
                }
                r[i] = max
            }
            let tempN = n
            while (tempN > 0) {
                let left = leftLength[tempN]
                solution.push(left)
                tempN -= left
            }
            console.log(solution.toString())
            return r[n]
        }
        console.log(cut_rod(9))
    </script>
</body>

</html>